// https://www.lintcode.com/problem/powx-n/description
// 428. x的n次幂
// 实现 pow(x,n)

// 样例
// Pow(2.1, 3) = 9.261
// Pow(0, 1) = 0
// Pow(1, 0) = 1
// 挑战
// O(logn) time

// 注意事项
// 不用担心精度，当答案和标准输出差绝对值小于1e-3时都算正确

class Solution {
public:
    /**
     * @param x: the base number
     * @param n: the power number
     * @return: the result
     */
    double myPow(double x, int n) {
        // O(n)
        // double result = 1;
        // int times = abs(n);
        // while (times-- && result < INT_MAX)
        // {
        //     result *= x;
        // }
        // if (n < 0)
        // {
        //     result = 1 / result;
        // }
        // return result;
        
        // 注意：
        // 输入
        // 2.00000
        // -2147483648
        // 期望答案
        // 0.00000
        
        // 法二： 时间复杂度O(logn)
        // 思路
        // • x 1 =x (1) =x 1
        // • x 2 =x (10) =x 2
        // • x 3 =x (11) =x 2 *x 1
        // • x 4 =x (100) =x 4
        // • x 5 =x (101) =x 4 *x 1
        // • x 6 =x (110) =x 4 *x 2
        
        // •x 1 =x 1
        // •(x 1 ) 2 =x 2
        // •(x 2 ) 2 =x 4
        // •(x 4 ) 2 =x 8
        // 十进制转二进制 %2    /2      
        // O(logn) time
        double *record = new double[1024];
        record[0] = 1;
        record[1] = x;
        double result = 1;
        int i = 1;
        if (n == INT_MIN)
        {
            return 0;
        }
        int times = abs(n);
       
        while (times)
        {
            int tmp = times % 2;
            if (signbit(x) == signbit(result * record[tmp * i]))
            {
                result *= record[tmp * i];
            }
            else
            {
                return 0;
            }
            times = times / 2;
            i++;
            record[i] = record[i - 1] * record[i - 1];
        }
        if (n < 0)
        {
            result = 1 / result;
        }
        return result;
    }
};